#include "dag.h"
// 去重
template<typename T>
void removeDuplicatesAndSort(std::vector<T>& vec) {
    std::set<T> uniqueElements(vec.begin(), vec.end());
    vec.assign(uniqueElements.begin(), uniqueElements.end());
}
// 是否是数字
bool isNumber(string s) {
    // 正则模式：匹配整数或浮点数
    const regex pattern(R"(^[+-]?(\d+(\.\d*)?|\.\d+)$)");
    return regex_match(s, pattern);
}
// 是否是临时变量
bool isTemp(string s) {
    const regex pattern(R"(^qtmp\d+$)");
    return regex_match(s, pattern);
}
// 设置优先级    数字常量>变量>临时变量
int priority(string str) {
    int p = -1;
    if (isNumber(str)) {
        p = 5;
    }
    else if (isTemp(str)){
        p = 1;
    }
    else {
        p = 3;
    }
    return p;
}
// 四元式（有参构造）
Quadruple::Quadruple(string op, string arg1, string arg2, string result)
    : op(op), arg1(arg1), arg2(arg2), result(result) {}
// DAG结点
DAGNode::DAGNode(string op_val, string var, DAGNode* l, DAGNode* r)
    :op(op_val), key_var(var), left(l), right(r)
{
    this->odeg = 0;
    this->add_var(var);
    id = next_id++;
}
// DAG 添加变量名
void DAGNode::add_var(string var) {
    if (find(var_names.begin(), var_names.end(), var) == var_names.end()) {
        var_names.push_back(var);
        if (var_names.size()>=2) {
            set_key_var();
        }
    }
}
// DAG 移除变量名
void DAGNode::remove_var(string var) {
    var_names.erase(std::remove(var_names.begin(), var_names.end(), var), var_names.end());
}
// DAG 设置核心变量名
void DAGNode::set_key_var() {
    int key1, key2;
    key1 = priority(key_var);
    key2 = priority(var_names.back());
    if (key2 > key1)	this->key_var = var_names.back();
}
int DAGNode::next_id = 0;
// 读取文件
bool DAG::readFromFile(string fileName)
{
    //Statistical line number, potential BUG: The last line has a newline symbol
    ifstream file(fileName, ios::in);
    if (!file)
    {
        cerr << "ERROR::Cannot open Quat File, at Quaternion::readFromFile" << endl;
        return false;
    }
    string line;
    int lineNum = 0;
    while (getline(file, line)) {
        lineNum++;
        if (line.empty() || line[0] == '#') continue;
        Quadruple quad;
        if (!parseQuadruple(line, quad)) {
            std::cerr << "警告：第 " << lineNum << " 行格式无效: " << line << std::endl;
            continue;
        }

        olds.push_back(quad);
    }
    file.close();
    return true;
}
// 解析四元式
bool DAG::parseQuadruple(string& line, Quadruple& quad) {
    istringstream iss(line);
    string token;
    vector<std::string> tokens;

    // 分割行到token
    while (iss >> token) {
        tokens.push_back(token);
    }

    // 根据token数量处理
    switch (tokens.size()) {
    case 1:
        quad = Quadruple(tokens[0], "", "", "");
        break;
    case 2:
        quad = Quadruple(tokens[0], tokens[1], "", "");
        break;
    case 3:
        quad = Quadruple(tokens[0], tokens[1], tokens[2], "");
        break;
    case 4:
        quad = Quadruple(tokens[0], tokens[1], tokens[2], tokens[3]);
        break;
    default:
        // 超过4个token的处理：合并后面的token到result
        if (tokens.size() > 4) {
            quad.op = tokens[0];
            quad.arg1 = tokens[1];
            quad.arg2 = tokens[2];
            // 合并剩余部分到result
            for (size_t i = 3; i < tokens.size(); i++) {
                if (i > 3) quad.result += " ";
                quad.result += tokens[i];
            }
        }
        else {
            return false;
        }
    }

    return true;
}
// 找入口（用于划分基本块）
void DAG::findLeaders() {
    this->leaders.push_back(0);
    for (int i = 1; i < this->olds.size(); i++) {
        Quadruple q = olds[i];
        string op = q.op;
        // 跳转的入口
        if (op == "jmp" ||op == "end"||op == "label"||op == "func") {  //
            this->leaders.push_back(i);
        }
        // 跳转的下一行
        if (op == "do" ||op == "goto"||op == "if"||op =="el"||op =="wh"||
            op == "dowhile"||op =="dowhcmp"||op == "call"||op == "re") { /* ||op == "label" */
            this->leaders.push_back(i+1);
        }
    }
    // 方便操作	添加最后一行的下一行
    this->leaders.push_back(this->olds.size());
    // 去重
    removeDuplicatesAndSort(this->leaders);
}
// 生成DAG
void DAG::generateDAGOptimizer() {
    DAGOptimizer* newBlock;
    for (int i = 0; i < this->leaders.size()-1; i++) {
        int begin, end;
        begin = this->leaders[i];
        end = this->leaders[i + 1];
        vector<Quadruple> tempQ(this->olds.begin() + begin, this->olds.begin() + end);
        newBlock = new DAGOptimizer(tempQ);
        if (tempQ[0].op == "func") {
            newBlock->is_func_entry = true;
        }
        this->dags.push_back(*newBlock);
    }
}
// 生成DAGOptimizer
void DAGOptimizer::generateDAG(vector<Quadruple> quat) {
    int cur_index = DAGNode::next_id;
    for (int i = 0; i < quat.size(); i++) {
        Quadruple q = quat[i];
        bool isnew = false;
        int a1=-1, a2=-1;
        DAGNode* left = nullptr;
        DAGNode* right = nullptr;
        string op = q.op;
        string arg1 = q.arg1;
        string arg2 = q.arg2;
        string result = q.result;
        if (arg1 != "#") {
            a1 = find_var(arg1);
            if (a1 == -1) {
                // 创建一个DAGNode
                isnew = true;
                left = new DAGNode("#", arg1);
                nodes.push_back(left);
                varMap[arg1] = left->id - cur_index;
            }
            else {
                left = nodes[a1];
                nodes[a1]->add_var(arg1);
                updateVar(a1, arg1);
                varMap[arg1] = a1;
            }
        }
        if (arg2 != "#") {
            a2 = find_var(arg2);
            if (a2 == -1) {
                // 创建一个DAGNode
                isnew = true;
                right = new DAGNode("#", arg2);
                nodes.push_back(right);
                varMap[arg2] = right->id - cur_index;
            }
            else {
                right = nodes[a2];
                nodes[a2]->add_var(arg2);
                updateVar(a2, arg2);
                varMap[arg2] = a2;
            }
        }
        if (op == "cout"|| op == "func" || op == "for"|| op == "[]="||op == "=[]"||op=="lable"||op=="end") {
            DAGNode* new_node = new DAGNode(op, result, left, right);
            nodes.push_back(new_node);
            continue;
        }else if (op == "if"){
            DAGNode* new_node = new DAGNode(op, result, left, right);
            if (left != nullptr) new_node->odeg++;
            if (right!= nullptr) new_node->odeg++;
            nodes.push_back(new_node);
            continue;
        }

        if (!isnew) {
            int a3 = find_parent(a1, a2, op);
            if (a3 == -1) {
                isnew = true;
            }
            else {
                nodes[a3]->add_var(result);
                updateVar(a3, result);
                varMap[result] = a3;
            }
        }
        if (isnew) {
            if (op == "=") {
                if (left != nullptr) {
                    left->add_var(result);
                    updateVar(left->id - cur_index, result);
                    varMap[result] = left->id - cur_index;
                }
            }
            else {
                // 创建新的DAGNode
                DAGNode* new_node = new DAGNode(op, result, left, right);
                nodes.push_back(new_node);
                varMap[result] = new_node->id - cur_index;
                // if (left != nullptr) left->ideg++;
                // if (right!= nullptr) right->ideg++;
                if (left != nullptr) new_node->odeg++;
                if (right!= nullptr) new_node->odeg++;
            }
        }
    }
}
// DAGOptimizer构造函数
DAGOptimizer::DAGOptimizer(vector<Quadruple> quat) {
    generateDAG(quat);
}
// 查找变量名所在的节点编号
int DAGOptimizer::find_var(string var) {
    int index = -1;
    auto it = varMap.find(var);
    if (it != varMap.end()) {
        index = it->second;
    }
    else {
        // std::cout << var + "not found!" << std::endl;
    }
    return index;
}
// 更新var 即去除当前修改的var之前所在的位置
void DAGOptimizer::updateVar(int index,string var) {
    for (int i = 0; i < nodes.size(); i++) {
        if (i != index) {
            nodes[i]->remove_var(var);
        }
    }
}
// 寻找父节点
int DAGOptimizer::find_parent(int index1, int index2, string op) {
    for (int i = nodes.size() - 1; i >= 0; i--) {
        DAGNode* node = nodes[i];
        if (node->op == op) {
            DAGNode* left = node->left;
            DAGNode* right = node->right;
            int l = -1, r = -1;
            if (left != nullptr) {
                l = find_var(left->key_var);
            }
            if (right != nullptr) {
                r = find_var(right->key_var);
            }
            if (l == index1 && r == index2) {
                return i;
            }
            else if (r == index1 && l == index2&&(op == "+" || op == "*")) {
                return i;
            }
        }
    }
    return -1;
}
vector<DAGNode*> DAGOptimizer::find_parent_dec(DAGNode* node){
    vector<DAGNode*> q;
    for(int i = 0;i<nodes.size();i++){
        if(nodes[i]->left == node){
            nodes[i]->odeg -= 1;
            if(nodes[i]->odeg == 0){
                q.push_back(nodes[i]);
            }
        }
        if(nodes[i]->right == node){
            nodes[i]->odeg -= 1;
            if(nodes[i]->odeg == 0){
                q.push_back(nodes[i]);
            }
        }
    }
    return q;
}
// 寻找节点包含的变量名
vector<string> DAGOptimizer::find_by_int(int i) {
    vector<string> varNames;
    for (const auto& pair : this->varMap) {
        if (pair.second == i) {
            varNames.push_back(pair.first);
        }
    }
    return varNames;
}
DAG::DAG() {

}
// 构造入口
DAG::DAG(vector<Quadruple> quat) {
    this->olds = quat;
    this->findLeaders();
    this->generateDAGOptimizer();
    this->generateNewQuad();
}
// 生成优化后的四元式
void DAG::generateNewQuad() {
    vector<DAGNode*> tnodes;
    DAGNode* tnode;
    Quadruple* tquad;
    for (int i = 0; i < dags.size(); i++) {
        tnodes = dags[i].nodes;
        // 出度为0的入队
        std::queue<DAGNode*> q;
        for (int j = 0; j < tnodes.size(); j++) {
            tnode = tnodes[j];
            if (tnode->odeg == 0) {
                q.push(tnode);
            }
        }
        // 3. 执行拓扑排序
        while (!q.empty()) {
            tnode = q.front();
            string op = "#", arg1, arg2, result;
            op = tnode->op;

            // 出度调整 并将新出度为0的结点 加入队列
            vector<DAGNode*> addnode = dags[i].find_parent_dec(tnode);
            for(int t = 0;t<addnode.size();t++){
                q.push(addnode[t]);
            }

            if (tnode->left != nullptr) {
                arg1 = tnode->left->key_var;
            }
            else     arg1 = "#";
            if (tnode->right != nullptr) {
                arg2 = tnode->right->key_var;
            }
            else    arg2 = "#";
            result = tnode->key_var;

            int k = tnode->id - tnodes[0]->id;
            vector<string> varNames = dags[i].nodes[k]->var_names;
            for (int t = 0; t < varNames.size(); t++) {
                string varName = varNames[t];
                if (varName != result && !isTemp(varName)) {
                    tquad = new Quadruple("=", result, "#", varName);
                    news.push_back(*tquad);
                }
            }
            if (op == "#" && arg1 == "#" && arg2 == "#") {

            }
            else {

                tquad = new Quadruple(op, arg1, arg2, result);
                news.push_back(*tquad);
            }
            q.pop();
        }
    }
}

// 写文件
bool DAG::wirte2File() {
    string filePath = "optimize.dat";
    // 打开文件
    fstream file(filePath, std::ios::out | std::ios::trunc);;
    if (!file.is_open()) {
        return false;
    }
    else {
        // 写入
        for (int i = 0; i < news.size(); i++) {
            file << news[i].op << " "
                 << news[i].arg1 << " "
                 << news[i].arg2 << " "
                 << news[i].result
                 << endl;
        }
        file.close();
        return true;
    }
}
